#include "expparser.h"
#include <cstdlib>
#include <vector>
#include <stack>
#include <QDebug>
#include "tool.h"

ExpParser::ExpParser(): idx(0){}

TreeNode* ExpParser::parser(std::string exp)
{
    str_exp = exp;

    //中缀表达式 转 后缀表达式
    std::stack<Token> ts;
    std::vector<Token> list_tok;

    while(idx < (int)str_exp.length())
    {
        Token token = nextToken();
        if(token.type == NUMBER)
        {
            list_tok.push_back(token);
            continue;
        }
        else if(token.type == LP)
        {
            ts.push(token);
            continue;
        }
        else if(token.type == RP)
        {
            while(!ts.empty() && ts.top().type != LP)
            {
                list_tok.push_back(ts.top());ts.pop();
            }
            ts.pop();//弹出左括号
            continue;
        }
        else if(token.type == OP || token.type == NAME)
        {
            if(!is_func_name(token.val_str) && token.type != OP)
            {
                list_tok.push_back(token);
                continue;
            }

            if(ts.empty())
            {
                ts.push(token);
            }
            else
            {
                while(!ts.empty() && op_level(ts.top().val_str) >= op_level(token.val_str))
                {
                    list_tok.push_back(ts.top());
                    ts.pop();
                }
                ts.push(token);
            }
        }
        else continue;
    }

    while(!ts.empty())
    {
        list_tok.push_back(ts.top());ts.pop();
    }

    //后缀表达式 转 表达式树
    std::stack<TreeNode*> stack_tree;
    for(Token element : list_tok)
    {
        if(element.type == NUMBER)//数字
        {
            stack_tree.push(new TreeNode(element.val_num));
        }
        else if(element.type == NAME && !is_func_name(element.val_str))//变量
        {
            stack_tree.push(new TreeNode(element.val_str));
        }
        else if(element.type == NAME && is_func_name(element.val_str))//函数
        {
            TreeNode *node = new TreeNode();
            node->op = element.val_str;
            node->childs["num"] = stack_tree.top();stack_tree.pop();
            stack_tree.push(node);
        }
        else if(element.type == OP)//运算符
        {
            TreeNode *node = new TreeNode();
            node->op = element.val_str;
            node->childs["num1"] = stack_tree.top();stack_tree.pop();
            node->childs["num2"] = stack_tree.top();stack_tree.pop();
            stack_tree.push(node);
        }
    }
    return stack_tree.top();
}

Token::Token(Token_Type type, std::string str): val_str(str), type(type){}
Token::Token(Token_Type type, float num): val_num(num), type(type){}

Token ExpParser::nextToken()
{
    char ch = curChar();
    char nch;
    switch (ch) {
    case 'a'...'z':
    case 'A'...'Z':
    case '_':
        return Token(NAME, readName());
        break;
    case '0'...'9':
        return Token(NUMBER, readNum());
        break;
    case '+':
    case '*':
    case '/':
    case '^':
        return Token(OP, std::string()+=getChar());
        break;
    case '-':
        nch = nextChar();
        if(nch >= '0' && nch <= '9')
        {
            getChar();
            return Token(NUMBER, -readNum());
        }
        else if(isalpha(nch) || nch == '(') return Token(NAME, std::string()+=getChar());
        else return Token(OP, std::string()+=getChar());
        break;
    case '(':
        return Token(LP, std::string()+=getChar());
        break;
    case ')':
        return Token(RP, std::string()+=getChar());
        break;
    default:
        idx++;
        return Token(NAME, "");
        break;
    }
}

float ExpParser::readNum()
{
    char ch = curChar();
    std::string num;
    if(ch == '-') num += getChar();
    while((ch >= '0' && ch <= '9') ||  ch == '.')
    {
        num += getChar();
        ch = curChar();
    }
    return atof(num.c_str());
}

std::string ExpParser::readName()
{
    char ch = curChar();
    std::string name;
    while((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9') || ch == '_')
    {
        name += getChar();
        ch = curChar();
    }
    return name;
}

char ExpParser::curChar()
{
    return str_exp[idx];
}

char ExpParser::getChar()
{
    return str_exp[idx++];
}

char ExpParser::nextChar()
{
    return str_exp[idx+1];
}
